public class KMPMatcher {
    /**
     * 计算模式串的next数组（部分匹配表）
     *
     * @param pattern 模式串
     * @return next数组
     */
    private static int[] computeNext(String pattern) {
        int[] next = new int[pattern.length()];
        next[0] = -1; // 初始化首位为-1
        int i = 0, j = -1; // i为后缀指针，j为前缀指针

        while (i < pattern.length() - 1) {
            if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                // 优化：避免重复比较相同字符[5](@ref)
                next[i] = (pattern.charAt(i) != pattern.charAt(j)) ? j : next[j];
            } else {
                j = next[j]; // 回溯前缀指针
            }
        }
        return next;
    }

    /**
     * KMP匹配主方法
     *
     * @param text    主文本
     * @param pattern 模式串
     * @return 首次匹配的起始位置，未找到返回-1
     */
    public static int search(String text, String pattern) {
        if (pattern.isEmpty()) return 0; // 空模式串直接匹配

        int[] next = computeNext(pattern);
        int i = 0, j = 0; // i主文本指针，j模式串指针

        while (i < text.length() && j < pattern.length()) {
            if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j]; // 利用next数组跳过已匹配部分[4](@ref)
            }
        }
        return (j == pattern.length()) ? i - j : -1;
    }
}